A common problem encountered when processing data that represents physical phenomena is computing a model of the phenomena from the data points, especially when the data points are corrupted with noise and other inaccuracies. For example, the phenomena can be a three dimensional physical scene that has been captured as one or more images from a camera that is in motion within the three dimensional physical scene. Other examples include any measurements of data from a physical system (e.g. data acquired via one or more sensors in a data acquisition system). One example includes seismic data captured in a system, where the seismic data can be processed to determine geological features underlying the surface.
Various methods for processing the data to compute the model often include statistical analysis of the data using a consensus estimator. The consensus estimator samples a minimal number of points from the data and attempts to compute a model that fits the sampled data. For example, a line model can be constructed from a sample of two or more points, and a plane model can be constructed from a sample of three or more points. The constructed model is then verified over all the data. Repeated sampling of the data and computing a best fit model may be performed, and the fit of the models to all of the data may be compared to select a best model out of the constructed models. Examples of such consensus estimators include RANSAC and some of its variants, such as progressive sample consensus (PROSAC), randomized RANSAC, progressive RANSAC, maximum likelihood estimation sample consensus (MLESAC or MAPSAC), N adjacent points random consensus (NAPSAC), importance sampling consensus (IMPSAC), and robust filtering by consensus (KALMANSAC).
The above methods may arrive at a solution given enough computational resources. However, when the inlier ratio is low (that is, the number of outliers is large compared to the number of inliers), the computational cost may be too high and a solution may not be achieved within a desired time frame.